package hot100.logos71To80;

import java.util.ArrayList;
import java.util.List;

/**
 * @author logos
 * date 2025/7/17 19:40
 * @version v1.0
 * @Package hot100.logos71To80
 */
public class logos80 {

    /**
     * 80. 划分字母区间
     * https://leetcode.cn/problems/partition-labels/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public List<Integer> partitionLabels(String s) {
            char[] sArr = s.toCharArray();
            int n = sArr.length;
            int[] last = new int[26];
            for (int i = 0; i < n; i++) {
                last[sArr[i] - 'a'] = i;
            }
            List<Integer> ans = new ArrayList<>();
            int start = 0;
            int end = 0;
            for (int i = 0; i < n; i++) {
                end = Math.max(end, last[sArr[i] - 'a']);
                if (i == end) {
                    ans.add(end - start + 1);
                    start = i + 1;
                }
            }
            return ans;
        }
    }
}
